﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace DataStuctureStudy.Heaps
{
    class HeapTest
    {
        public static void Test()
        {
            var heap = new Heap<int>(10);
            heap.Insert(1);
            heap.Insert(2);
            heap.Insert(3);
            heap.Insert(4);
            heap.Insert(5);
            heap.Insert(6);
            heap.Display();
            heap.Remove();
            heap.Display();
        }

        class Heap<T>
            where T : IComparable<T>
        {
            private T[] _items;
            private int _length;

            public Heap(int size)
            {
                _items = new T[size];
            }

            public void Display()
            {
                Console.WriteLine("数组表示");
                Console.Write("[");
                for (var i = 0; i < _items.Length; i++)
                {
                    if (i < _length)
                    {
                        Console.Write(_items[i]);
                    }
                    else
                    {
                        Console.Write('-');
                    }
                }
                Console.WriteLine("]");
                Console.WriteLine();

                Console.WriteLine("树形表示");
                var row = 0;
                var column = 0;
                var level = (int)Math.Ceiling(Math.Log(_length + 1, 2));
                var width = (int)Math.Pow(2, level);
                for (var i = 0; i < _length; i++)
                {
                    this.Display(_items[i], width, row, column);

                    if ((i + 1) == Math.Pow(2, row + 1) - 1)
                    {
                        row++;
                        column = 0;
                        Console.WriteLine();
                    }
                    else
                    {
                        column++;
                        if (i == _length - 1)
                        {
                            Console.WriteLine();
                        }
                    }
                }

                Console.WriteLine();
            }

            private void Display(T item, int width, int row, int column)
            {
                var step = (int)((width * 3) / Math.Pow(2, row));
                var itemLength = item.ToString().Length;
                Console.Write(item.ToString().PadLeft((step + itemLength) / 2).PadRight(step));
            }

            public void Insert(T item)
            {
                if (this.IsFull())
                {
                    throw new InvalidOperationException("容量已满，不能插入！");
                }

                _items[_length++] = item;
                this.MoveUp(_length - 1);
            }

            private void MoveUp(int index)
            {
                var bottom = _items[index];
                var current = index;

                while (current > 0)
                {
                    var parent = (current - 1) / 2;
                    if (_items[parent].CompareTo(bottom) > 0)
                    {
                        break;
                    }

                    _items[current] = _items[parent];
                    current = parent;
                }

                _items[current] = bottom;
            }

            public T Remove()
            {
                if (this.IsEmpty())
                {
                    throw new InvalidOperationException("容量已空，不能删除！");
                }

                var result = _items[0];
                _items[0] = _items[--_length];
               
                this.MoveDown(0);

                return result;
            }

            private void MoveDown(int index)
            {
                var top = _items[index];
                var current = index;

                while (current < _length)
                {
                    var large = 0;
                    var left = 2 * current + 1;
                    var right = left + 1;

                    if (left < _length && right < _length)
                    {
                        if (_items[left].CompareTo(_items[right]) >= 0)
                        {
                            large = left;
                        }
                        else
                        {
                            large = right;
                        }
                    }
                    else if (left < _length)
                    {
                        large = left;
                    }
                    else
                    {
                        break;
                    }

                    if (_items[large].CompareTo(top) <= 0)
                    {
                        break;
                    }

                    _items[current] = _items[large];
                    current = large;
                }

                _items[current] = top;
            }

            public bool IsFull()
            {
                return _length == _items.Length;
            }

            public bool IsEmpty()
            {
                return _length == 0;
            }
        }
    }
}
